Asymmetric cryptography, also known as public-key cryptography, is a subset of cryptography that refers to cryptographic processes requiring two separate keys. One key, called the private key, is used to decrypt and sign messages. The other key, called the public key, is used to encrypt messages and verify message signatures. As their name suggests, the private key is privately kept by a single entity, whereas the public key is usually distributed to many different entities. Let's call Alice the entity that owns the private key, and Bob any entity that has a copy of the public key. Thanks to this asymmetric setup, any entity can send a confidential message to Alice, but only she can decrypt it. Also, if Alice signs a message, any entity may check that the message was not tampered with by verifying the signature using Alice's public key. If this verification succeeds, then it also means that Alice did sign the message since only her private key can generate valid signatures for that public key (this process is known as non-repudiation).
A well-known asymmetric cryptographic process is RSA. Let *N denotes the set of integers {1, 2, . . . , N−1}, and N=pq be the product of two primes of equal size. N is called the RSA modulus. An RSA public key is the pair <N,e> where e is usually chosen in the set {3, 17, 216+1}. The corresponding RSA private key is the pair <N,d>, where d is computed such that for any integer Mε*N, we have Med mod N=M. To compute d, Alice first computes the Euler totient function φ(N)=(p−1)(q−1), then computes d as the multiplicative inverse of e modulo φ(N), that is, d=e−1 mod φ(N).
After this set up phase, the encryption and decryption operations are straightforward. In RSA, the plaintext message is represented by an integer Mε*N. To encrypt that message using Alice's key, Bob ComputesC=Me mod N which produces the ciphertext C. When Alice receives this message, she performs the reverse operation using her private key, that is,M=Cd mod N 
The operations above are usually implemented in an electronic device. We focus below on the process and device used for signing or decrypting messages using Alice's private key. Besides performing these operations of signing or decrypting, these process and devices may also be used to protect the confidentiality of the private key against a malicious attacker that we will call Marvin, trying to eavesdrop or to tamper with the communication between Alice and Bob. Marvin's attack succeeds if he manages to sign or decrypt a message without Alice's consent. The most serious attack is the attack in which Marvin succeeds in extracting Alice's private key from the device itself.
There are many known methods for attempting this attack. For instance, Marvin may observe power consumption or electro-magnetic emissions of the device and extract the bits of the private keys using side-channel analysis. Marvin may also manipulate the device, change the operating conditions or tamper with essential components of the device so that the device outputs part of its memory content. This could happen, for instance, if at the time the message is output by the device, the pointer containing the address of the decrypted message is corrupted to point to a random address in memory. The attack succeeds if this address is within the memory zone containing Alice's private key.
Note that Marvin does not need to guess all the bits of the private key to succeed. Partial key exposure attacks allow attacker to recover the entire private key from only a partial knowledge of the key bits. First it is well-known that when the public key exponent, e, is small, then the RSA system leaks half of the most significant bits of the corresponding private key exponent, d; see Dan Boneh, ‘Twenty years of attacks on the RSA cryptosystem’, Notice of the AMS, page 203-213, February 1999. In another paper, Boneh et al. demonstrated the following theorem stating that Marvin can retrieve the full private key exponent from only a fraction of the least significant bits, as long as the corresponding public key is small, see Dan Boneh, et al. ‘Exposing an RSA private key given a small fraction of its bits’, (K. Ohta and D. Pei, eds), vol. 1514, 1998, pages 25-34.
Boneh, et al.'s theorem is: Let N, dbe a private RSA key in which N is n bits long. Given the ┌n/4┐ least significant bits of d, Marvin can reconstruct all of d in a time linear in e log2 e.
The attack based on the theorem above works if Marvin knows the n/4 least significant bits of d. Conversely, we can show a similar result if Marvin knows all bits except for these n/4 least significant bits. There are many other variants of this attack.
There are also a variety of known countermeasures to oppose these attacks. One such countermeasure is secret sharing, also known as multi-party computation. In that method, the private key d, is split into several secret parts d1, d2, . . . , dk that are all used independently. Each key produce an intermediate message after decryption of the cipher-text, and these intermediate messages are then combined together to obtain the original clear-text message. This process is such that each private key share does not reveal any information about the original private key, and in the same way, each intermediate message does not disclose any information about the origin clear-text message. FIG. 1 illustrates the secret sharing concept. In FIG. 1, each exponentiation Cdi+, with i=1, 2, 3 can be done in parallel and by separate entities to reduce the chance that an attacker obtains access to all secret shares.
Secret sharing usually exploits another property of the private exponent d, which is that there are infinitely many equivalent private exponents d′ that can be used to decrypt a ciphertext. Let kεN and d′=d+kφ(N). From Euler's theorem, we have that Cφ(N) mod N=1, and hence Cd′≡Cd+kφ(N)≡Cd 1k≡Cd (mod N).
In symmetric cryptography the usual way to implement secret-sharing is to split the symmetric key into several parts that are XOR-ed, that is bitwise added together, to give back the original key. The same method can be used with RSA by replacing the XOR operation with a regular integer addition. The RSA private key can then be split in k parts d1+, d2+, . . . , dk+ as follows:
                              d          i          +                =                  {                                                                      chosen                  ⁢                                                                          ⁢                  arbitrarily                                                                                                                        if                      ⁢                                                                                          ⁢                      1                                        ≤                    i                    <                    k                                    ,                                                                                                                          (                                          d                      -                                                                        Σ                          1                                                      k                            -                            1                                                                          ⁢                                                  d                          i                                                                                      )                                    ⁢                                                                          ⁢                  mod                  ⁢                                                                          ⁢                                      φ                    ⁡                                          (                      N                      )                                                                                                                                        if                    ⁢                                                                                  ⁢                    i                                    =                                      k                    .                                                                                                          (        1        )            
The decryption using these shares is done as follows. First the ciphertext is decrypted using each key part separately to produce intermediate messages Mi, with 1≦i≦k. Then all messages are multiplied together to obtain the original cleartext message. We have
            M      1        =                  C                  d          1          +                    ⁢                          ⁢      mod      ⁢                          ⁢      N                  M      2        =                  C                  d          2          +                    ⁢                          ⁢      mod      ⁢                          ⁢      N        …            M      k        =                  C                  d          k          +                    ⁢                          ⁢      mod      ⁢                          ⁢      N            M    =                            M          1                ·                  M          2                    ⁢                          ⁢      …      ⁢                          ⁢              M        k            ⁢                          ⁢      mod      ⁢                          ⁢      N      
The method is illustrated, as mentioned before, in FIG. 1. Splitting the private key into multiple parts increases the number of bits the attacker has to guess. In addition, depending on the attack settings, the secret sharing may make the job of the attacker much harder or even impossible.
To protect against partial key exposure, a known technique is to extend the size of the private exponent by applying the Euler's theorem. For instance, let r be a 64-bit random integer. The idea consists in applying the secret sharing not to d directly but to d′=d+rφ(N). We have then as secret shares of the private key
                              d          i          +                =                  {                                                                      chosen                  ⁢                                                                          ⁢                  arbitrarily                                                                                                                        if                      ⁢                                                                                          ⁢                      1                                        ≤                    i                    <                    k                                    ,                                                                                                                          d                    ′                                    -                                      (                                                                  Σ                        1                                                  k                          -                          1                                                                    ⁢                                              d                        i                        +                                            ⁢                                                                                          ⁢                      mod                      ⁢                                                                                          ⁢                                              φ                        ⁡                                                  (                          N                          )                                                                                      )                                                                                                                    if                    ⁢                                                                                  ⁢                    i                                    =                                      k                    .                                                                                                          (        2        )            